package com.ztom.v2;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ZhangTao
 */
public class Code11SlidingWindowMaximum {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];

        Deque<Integer> queue = new ArrayDeque<>();
        for (int l = 0, r = 0; r < n; r++) {
            // 把窗口内小于当前值的都丢弃
            while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[r]) {
                queue.pollLast();
            }
            // 当前值写入
            queue.addLast(r);

            // 窗口形成中
            if (r < k - 1) {
                continue;
            }

            // 窗口过期
            if (queue.peekFirst() <= r - k) {
                queue.pollFirst();
            }

            // 窗口滑动
            res[l++] = nums[queue.peekFirst()];
        }

        return res;
    }
}
